package __回溯算法

/**
https://leetcode.cn/problems/letter-combinations-of-a-phone-number/

17. 电话号码的字母组合
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

示例 1：
输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]

示例 2：
输入：digits = ""
输出：[]

示例 3：
输入：digits = "2"
输出：["a","b","c"]
*/

var (
	m    []string
	path []byte
	res  []string
)

func letterCombinations(digits string) []string {
	//输入参数列表
	m = []string{"abc", "def", "ghi", "jkl",
		"mno", "pqrs", "tuv", "wxyz"}
	path, res = make([]byte, 0), make([]string, 0)

	//如果没有数字元素, 直接返回空即可
	if digits == "" {
		return res
	}

	//传入参数数组, 从0下标开始
	dfs(digits, 0)
	return res
}

func dfs(digits string, curIndex int) {
	//如果 path已经达到数字字符串长度
	if len(path) == len(digits) { //终止条件，字符串长度等于digits的长度
		temp := string(path)    //将path转为字符串
		res = append(res, temp) //path添加进结果数组
		return
	}

	//将字符串中的字符-->数字
	digit := int(digits[curIndex] - '0') // 将index指向的数字转为int（确定下一个数字）
	str := m[digit-2]                    // 取数字对应的字符集（注意和map中的对应）

	//遍历数字字符串元素: 递归调用+回溯操作
	for i := 0; i < len(str); i++ {
		path = append(path, str[i])
		dfs(digits, curIndex+1)
		path = path[:len(path)-1]
	}
}
